package com.hello;

/**
 * 桶排序
 * 适合数据量小、数据跨度不大的数据集排序
 * 算法步骤：
 * 定义一个桶
 * 定义一个数组，并把数组元素放入桶中
 *
 * 时间复杂度：
 *  O(N)
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 6, 4, 2, 8, 8};
        int[] bucket = new int[100];

        bucketSort(bucket, arr);

        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] > 0) {
                System.out.println("数 = " + i + ",个数 = " + bucket[i]);
            }
        }
    }

    public static void bucketSort(int[] bucket, int[] arr) {

        for (int i = 0; i < arr.length; i++) {
            if (bucket[arr[i]] >= 1) {
                bucket[arr[i]] = bucket[arr[i]] + 1;
            } else {
                bucket[arr[i]] = 1;
            }

        }
    }
}
